using System.Collections.Generic;
using UnityEngine;


namespace Super
{
	public class BinaryTree<T>
	{
		public BinaryTreeNode<T> root;

		public BinaryTree()
		{

		}
		public BinaryTree(T value)
		{
			Insert(value);
		}
		public BinaryTree(List<T> values)
		{
			foreach (T value in values)
			{
				Insert(value);
			}
		}

		/// <summary>
		/// 插入，层先法查找，第一个左子树或右子树为null的节点插入
		/// </summary>
		/// <param name="value"></param>
		public virtual void Insert(T value)
		{
			if (root == null)
			{
				root = new BinaryTreeNode<T>(value);
				return;
			}

			Queue<BinaryTreeNode<T>> queue = new Queue<BinaryTreeNode<T>>();
			queue.Enqueue(root);
			root = Insert(queue, value);
		}

		private BinaryTreeNode<T> Insert(Queue<BinaryTreeNode<T>> queue, T value)
		{
			BinaryTreeNode<T> root = queue.Dequeue();
			queue.Enqueue(root.left);
			queue.Enqueue(root.right);
			bool nextInsert = root.left != null && root.right != null;
			if (root.left == null)
				root.left = new BinaryTreeNode<T>(value);
			else if (root.right == null)
				root.right = new BinaryTreeNode<T>(value);

			if (nextInsert)
				Insert(queue, value);

			UpdateHeight(root);
			return root;
		}

		/// <summary>
		/// 删除节点
		/// 找到对应的节点
		/// 若非叶子节点，将节点子节点最下面的叶子结点替换
		/// 若是叶子节点，直接删除
		/// </summary>
		/// <param name="value"></param>
		public virtual void Delete(T value)
		{

			if (root == null)
				return;
			root = Delete(root, value);
		}

		private BinaryTreeNode<T> Delete(BinaryTreeNode<T> root, T value)
		{
			if (root.value.Equals(value))
			{
				if (root.left == null && root.right == null)
					return null;

				BinaryTreeNode<T> swapNode = root.left == null ? root.right : root.left;
				while (swapNode.left != null || swapNode.right != null)
				{
					swapNode = swapNode.left == null ? swapNode.right : swapNode.left;
				}
				root.value = swapNode.value;
				swapNode.value = value;
			}

			if (root.left != null)
				root.left = Delete(root.left, value);
			if (root.right != null)
				root.right = Delete(root.right, value);

			UpdateHeight(root);
			return root;
		}

		/// <summary>
		/// 按层先法，即广度优先查找
		/// </summary>
		/// <param name="value"></param>
		/// <returns></returns>
		public virtual BinaryTreeNode<T> Find(T value)
		{
			BinaryTreeNode<T> node = null;
			if (root == null)
				return node;

			Queue<BinaryTreeNode<T>> queue = new Queue<BinaryTreeNode<T>>();
			queue.Enqueue(root);

			while (queue.Count > 0)
			{
				node = queue.Dequeue();
				if (node.value.Equals(value))
					return node;

				if (node.left != null)
					queue.Enqueue(node.left);

				if (node.right != null)
					queue.Enqueue(node.right);
			}

			return node;
		}

		/// <summary>
		/// 前序遍历
		/// </summary>
		/// <returns></returns>
		public List<T> PreOrder()
		{
			List<T> list = new List<T>();
			PreorderRecursive(root, list);
			return list;
		}

		/// <summary>
		/// 中序遍历
		/// </summary>
		/// <returns></returns>
		public List<T> InOrder()
		{
			List<T> list = new List<T>();
			InorderRecursive(root, list);
			return list;
		}

		/// <summary>
		/// 后序遍历
		/// </summary>
		/// <returns></returns>
		public List<T> PostOrder()
		{
			List<T> list = new List<T>();
			PostorderRecursive(root, list);
			return list;
		}

		/// <summary>
		/// 层先法遍历
		/// </summary>
		/// <returns></returns>
		public List<T> LevOrder()
		{
			List<T> list = new List<T>();
			if (root == null)
				return list;

			Queue<BinaryTreeNode<T>> queue = new Queue<BinaryTreeNode<T>>();
			queue.Enqueue(root);
			LevOrderRecursive(queue, list);

			return list;
		}

		/// <summary>
		/// 获取平衡因子，左子树高度减右子数的高度
		/// </summary>
		/// <param name="node"></param>
		/// <returns></returns>
		public int BalanceFactor(BinaryTreeNode<T> node)
		{
			return Height(node.left) - Height(node.right);
		}

		/// <summary>
		/// 获取节点的高度，null的话为0，默认为1
		/// </summary>
		/// <param name="node"></param>
		/// <returns></returns>
		public int Height(BinaryTreeNode<T> node)
		{
			if (node == null) return 0;
			return node.height;
		}

		/// <summary>
		/// 根据子节点更新树的高度
		/// </summary>
		/// <param name="node"></param>
		/// <returns></returns>
		public int UpdateHeight(BinaryTreeNode<T> node)
		{
			node.height = Mathf.Max(Height(node.left), Height(node.right)) + 1;
			return node.height;
		}

		private void PreorderRecursive(BinaryTreeNode<T> root, List<T> list)
		{
			if (root == null)
				return;

			list.Add(root.value);
			PreorderRecursive(root.left, list);
			PreorderRecursive(root.right, list);
		}

		private void InorderRecursive(BinaryTreeNode<T> root, List<T> list)
		{
			if (root == null)
				return;

			InorderRecursive(root.left, list);
			list.Add(root.value);
			InorderRecursive(root.right, list);
		}

		private void PostorderRecursive(BinaryTreeNode<T> root, List<T> list)
		{
			if (root == null)
				return;

			PostorderRecursive(root.left, list);
			PostorderRecursive(root.right, list);
			list.Add(root.value);
		}

		private void LevOrderRecursive(Queue<BinaryTreeNode<T>> queue, List<T> list)
		{
			BinaryTreeNode<T> root = queue.Dequeue();
			list.Add(root.value);

			if (root.left != null)
				queue.Enqueue(root.left);
			if (root.right != null)
				queue.Enqueue(root.right);

			if (queue.Count > 0)
				LevOrderRecursive(queue, list);
		}
	}

}
